home *** CD-ROM | disk | FTP | other *** search
/ HPAVC / HPAVC CD-ROM.iso / pc / MCASM.RAR / MC_ASM.EXE / WROX_ASM / CH12 / FORMATS / PALETTE.CPP < prev    next >
Encoding:
C/C++ Source or Header  |  1994-06-16  |  11.7 KB  |  394 lines
  1. // The color_selector class implementation
  2. #include <mem.h>
  3. #include <alloc.h>
  4. #include "common.h"
  5. #include "graph.h"
  6. #include "palette.h"
  7.  
  8. void color_selector::prescan_line (BYTE *R, BYTE *G, BYTE *B) {
  9.  
  10.     BYTE *ptr0, *ptr1, *ptr2;     //I do know, how many registers are
  11.     register histptr histp;        //are in PC, but...
  12.     register int c0, c1, c2;
  13.     int col;     //col-umn, not color!
  14.         ptr0 = R;
  15.         ptr1 = G;
  16.         ptr2 = B;
  17.         for (col = width; col > 0; col--) {
  18.             /* get pixel value and index into the histogram */
  19.             c0 = (*ptr0++) >> R_SHIFT;
  20.             c1 = (*ptr1++) >> G_SHIFT;
  21.             c2 = (*ptr2++) >> B_SHIFT;
  22.             histp = & histogram[c0][c1][c2];
  23.             /* increment, check for overflow and undo increment if so. */
  24.             /* We assume unsigned representation here! */
  25.             if (++(*histp) == 0) (*histp)--;
  26.         }
  27. }
  28.  
  29. void color_selector::prepare_scan_palette (BGRpalette pal) {
  30.     int i;
  31.     for (i = 0; i < 256; i++) {
  32.         my_colormap[i].r = pal[i].r  >> R_SHIFT;
  33.         my_colormap[i].g = pal[i].g  >> G_SHIFT;
  34.         my_colormap[i].b = pal[i].b  >> B_SHIFT;
  35.         }
  36. }
  37.  
  38. void color_selector::prescan_line_palette (BYTE *source) {
  39.     register histptr histp;
  40.     register int  c0, c1, c2;
  41.     BGRcolortype color;
  42.     int col;     //col-umn, not color!
  43.         for (col = width; col > 0; col--) {
  44.             /* get pixel value and index into the histogram */
  45.             color = my_colormap[*(source++)];
  46.             c0 = color.r;
  47.             c1 = color.g;
  48.             c2 = color.b;
  49.             histp = & histogram[c0][c1][c2];
  50.             /* increment, check for overflow and undo increment if so. */
  51.             /* We assume unsigned representation here! */
  52.             if (++(*histp) == 0) (*histp)--;
  53.         }
  54. }
  55.  
  56.  
  57. /*
  58.  * Now we have the really interesting routines: selection of a colorhist
  59.  * given the completed histogram.
  60.  * These routines work with a list of "boxes", each representing a rectangular
  61.  * subset of the input color space (to histogram precision).
  62.  */
  63.  
  64. boxptr color_selector::find_biggest_color_pop() {
  65. /* Find the splittable box with the largest color population */
  66. /* Returns NULL if no splittable boxes remain */
  67.  
  68.   register boxptr boxp;
  69.   register int i;
  70.   register long maxc = 0;
  71.   boxptr which = NULL;
  72.  
  73.   for (i = 0, boxp = boxlist; i < numboxes; i++, boxp++) {
  74.     if (boxp->colorcount > maxc) {
  75.       if (boxp->splitable) {
  76.     which = boxp;
  77.     maxc = boxp->colorcount;
  78.       }
  79.     }
  80.   }
  81.   return which;
  82. }
  83.  
  84. boxptr color_selector:: find_biggest_volume () {
  85. /* Find the splittable box with the largest (scaled) volume */
  86. /* Returns NULL if no splittable boxes remain */
  87.  
  88.   register boxptr boxp;
  89.   register int i;
  90.   register long maxv = 0;
  91.   register long norm, c0,c1,c2;
  92.   boxptr which = NULL;
  93.  
  94.   /* We use 2-norm rather than real volume here.
  95.    * Some care is needed since the differences are expressed in
  96.    * histogram-cell units; if HIST_Y_BITS != HIST_C_BITS, we have to
  97.    * adjust the scaling to get the proper scaled-YCbCr-space distance.
  98.    * This code won't work right if HIST_Y_BITS < HIST_C_BITS,
  99.    * but that shouldn't ever be true.
  100.    * Note norm > 0 iff box is splittable, so need not check separately.
  101.    *  original volume calculation
  102.    * c0 = (boxp->c0max - boxp->c0min) * Y_SCALE;
  103.    * c1 = (boxp->c1max - boxp->c1min) << (HIST_Y_BITS-HIST_C_BITS);
  104.    * c2 = (boxp->c2max - boxp->c2min) << (HIST_Y_BITS-HIST_C_BITS);
  105.    * norm = c0*c0 + c1*c1 + c2*c2;
  106.    * Alas, it's not right for my volume - E.P., see update_box
  107.    */
  108.  
  109.   for (i = 0, boxp = boxlist; i < numboxes; i++, boxp++) {
  110.     norm = boxp->volume;
  111.     if ((boxp->splitable) && (norm > maxv)) {
  112.       which = boxp;
  113.       maxv = norm;
  114.     }
  115.   }
  116.   return which;
  117. }
  118.  
  119. void color_selector::update_box (boxptr boxp) {
  120. /* Shrink the min/max bounds of a box to enclose only nonzero elements, */
  121. /* and recompute its population */
  122.   histptr histp;
  123.   int c0,c1,c2;
  124.   int c0min,c0max,c1min,c1max,c2min,c2max;
  125.   unsigned long ccount;
  126.  
  127.   c0min = boxp->c0min;  c0max = boxp->c0max;
  128.   c1min = boxp->c1min;  c1max = boxp->c1max;
  129.   c2min = boxp->c2min;  c2max = boxp->c2max;
  130.   if (c0max > c0min)
  131.     for (c0 = c0min; c0 <= c0max; c0++)
  132.       for (c1 = c1min; c1 <= c1max; c1++) {
  133.     histp = & histogram[c0][c1][c2min];
  134.     for (c2 = c2min; c2 <= c2max; c2++)
  135.       if (*histp++ != 0) {
  136.         boxp->c0min = c0min = c0;
  137.         goto have_c0min;
  138.       }
  139.       }
  140.  have_c0min:
  141.   if (c0max > c0min)
  142.     for (c0 = c0max; c0 >= c0min; c0--)
  143.       for (c1 = c1min; c1 <= c1max; c1++) {
  144.     histp = & histogram[c0][c1][c2min];
  145.     for (c2 = c2min; c2 <= c2max; c2++)
  146.       if (*histp++ != 0) {
  147.         boxp->c0max = c0max = c0;
  148.         goto have_c0max;
  149.       }
  150.       }
  151.  have_c0max:
  152.   if (c1max > c1min)
  153.     for (c1 = c1min; c1 <= c1max; c1++)
  154.       for (c0 = c0min; c0 <= c0max; c0++) {
  155.     histp = & histogram[c0][c1][c2min];
  156.     for (c2 = c2min; c2 <= c2max; c2++)
  157.       if (*histp++ != 0) {
  158.         boxp->c1min = c1min = c1;
  159.         goto have_c1min;
  160.       }
  161.       }
  162.  have_c1min:
  163.   if (c1max > c1min)
  164.     for (c1 = c1max; c1 >= c1min; c1--)
  165.       for (c0 = c0min; c0 <= c0max; c0++) {
  166.     histp = & histogram[c0][c1][c2min];
  167.     for (c2 = c2min; c2 <= c2max; c2++)
  168.       if (*histp++ != 0) {
  169.         boxp->c1max = c1max = c1;
  170.         goto have_c1max;
  171.       }
  172.       }
  173.  have_c1max:
  174.   if (c2max > c2min)
  175.     for (c2 = c2min; c2 <= c2max; c2++)
  176.       for (c0 = c0min; c0 <= c0max; c0++) {
  177.     histp = & histogram[c0][c1min][c2];
  178.     for (c1 = c1min; c1 <= c1max; c1++, histp += HIST_B_ELEMS)
  179.       if (*histp != 0) {
  180.         boxp->c2min = c2min = c2;
  181.         goto have_c2min;
  182.       }
  183.       }
  184.  have_c2min:
  185.   if (c2max > c2min)
  186.     for (c2 = c2max; c2 >= c2min; c2--)
  187.       for (c0 = c0min; c0 <= c0max; c0++) {
  188.     histp = & histogram[c0][c1min][c2];
  189.     for (c1 = c1min; c1 <= c1max; c1++, histp += HIST_B_ELEMS)
  190.       if (*histp != 0) {
  191.         boxp->c2max = c2max = c2;
  192.         goto have_c2max;
  193.       }
  194.       }
  195.  have_c2max:
  196.  
  197.   /* Now scan remaining volume of box and compute population */
  198.   ccount = 0;
  199.   for (c0 = c0min; c0 <= c0max; c0++)
  200.     for (c1 = c1min; c1 <= c1max; c1++) {
  201.       histp = & histogram[c0][c1][c2min];
  202.       for (c2 = c2min; c2 <= c2max; c2++, histp++)
  203.         //    if (*histp != 0)  ccount ++;
  204.       ccount += *histp;
  205.     }
  206.   boxp->colorcount = ccount;
  207.   boxp->splitable = (c0max > c0min || c1max > c1min || c2max > c2min);
  208.  
  209.   // this was added by E.P.
  210.   // assumed HIST_G_BITS >= HIST_R_BITS >= HIST_B_BITS !!!
  211.  
  212.     c0 = ((c0max - c0min + 1) << (HIST_G_BITS-HIST_R_BITS)) * RSCALE >> 4;
  213.     c1 = (c1max - c1min + 1) * GSCALE >> 4;
  214.     c2 = (c2max - c2min + 1) << (HIST_G_BITS-HIST_B_BITS);
  215.     boxp->volume = c0*c0 + c1*c1 + c2*c2;
  216. }
  217.  
  218.  
  219. void color_selector:: median_cut () {
  220. /* Repeatedly select and split the largest box until we have enough boxes */
  221.  
  222.   int n,lb;
  223.   int c0,c1,c2,cmax;
  224.   register boxptr b1,b2;
  225.  
  226.   while (numboxes < desired_colors) {
  227.     /* Select box to split */
  228.     /* Current algorithm: by population for first half, then by volume */
  229.     if (numboxes*2 <= desired_colors) {
  230.       b1 = find_biggest_color_pop();
  231.     } else {
  232.       b1 = find_biggest_volume();
  233.     }
  234. //    if (numboxes >= 131)    lb = numboxes;
  235.  
  236.     if (b1 == NULL)        /* no splittable boxes left! */
  237.       break;
  238.     b2 = &boxlist[numboxes];    /* where new box will go */
  239.     /* Copy the color bounds to the new box. */
  240.  
  241.     b2->c0max = b1->c0max; b2->c1max = b1->c1max; b2->c2max = b1->c2max;
  242.     b2->c0min = b1->c0min; b2->c1min = b1->c1min; b2->c2min = b1->c2min;
  243.  
  244.     /* Choose which axis to split the box on.
  245.      * Current algorithm: longest scaled axis.
  246.      * See notes in find_biggest_volume about scaling...
  247.      */
  248.  
  249.     // and selected axe is to be splittable!!! - E.P.
  250.  
  251.     if  ((c0 = b1->c0max - b1->c0min) > 0)
  252.     c0 = ((c0+1) << (HIST_G_BITS-HIST_R_BITS)) * RSCALE >> 4;
  253.     if  ((c1 = b1->c1max - b1->c1min) > 0)
  254.     c1 = (c1+1)  * GSCALE >> 4;
  255.     if  ((c2 = b1->c2max - b1->c2min) > 0)
  256.     c2 = (c2 + 1) << (HIST_G_BITS-HIST_B_BITS);
  257.     cmax = c0; n = 0;
  258.     if (c1 > cmax) { cmax = c1; n = 1; }
  259.     if (c2 > cmax) { n = 2; }
  260.     /* Choose split point along selected axis, and update box bounds.
  261.      * Current algorithm: split at halfway point.
  262.      * (Since the box has been shrunk to minimum volume,
  263.      * any split will produce two nonempty subboxes.)
  264.      * Note that lb value is max for lower box, so must be < old max.
  265.      */
  266.  
  267.     switch (n) {
  268.     case 0:
  269.       lb = (b1->c0max + b1->c0min) / 2;
  270.       b1->c0max = lb;
  271.       b2->c0min = lb+1;
  272.       break;
  273.     case 1:
  274.       lb = (b1->c1max + b1->c1min) / 2;
  275.       b1->c1max = lb;
  276.       b2->c1min = lb+1;
  277.       break;
  278.     case 2:
  279.       lb = (b1->c2max + b1->c2min) / 2;
  280.       b1->c2max = lb;
  281.       b2->c2min = lb+1;
  282.       break;
  283.     }
  284.     /* Update stats for boxes */
  285.     update_box(b1);
  286.     update_box(b2);
  287.     numboxes++;
  288.   }
  289. }
  290.  
  291.  
  292. void color_selector:: compute_color (boxptr boxp, BGRcolortype &color) {
  293.  
  294. /* Compute representative color for a box, put it in my_colorhist[icolor] */
  295. /* Current algorithm: mean weighted by pixels (not colors) */
  296. /* Note it is important to get the rounding correct! */
  297.   histptr histp;
  298.   int c0,c1,c2;
  299.   int c0min,c0max,c1min,c1max,c2min,c2max;
  300.   long count;
  301.   long total = 0;
  302.   long c0total = 0;
  303.   long c1total = 0;
  304.   long c2total = 0;
  305.  
  306.     c0min = boxp->c0min;  c0max = boxp->c0max;
  307.     c1min = boxp->c1min;  c1max = boxp->c1max;
  308.     c2min = boxp->c2min;  c2max = boxp->c2max;
  309.  
  310.    for (c0 = c0min; c0 <= c0max; c0++)
  311.     for (c1 = c1min; c1 <= c1max; c1++) {
  312.       histp = & histogram[c0][c1][c2min];
  313.       for (c2 = c2min; c2 <= c2max; c2++) {
  314.     if ((count = *histp++) != 0) {
  315.       total += count;
  316.       c0total += ((c0 << R_SHIFT) + ((1<<R_SHIFT)>>1)) * count;
  317.       c1total += ((c1 << G_SHIFT) + ((1<<G_SHIFT)>>1)) * count;
  318.       c2total += ((c2 << B_SHIFT) + ((1<<B_SHIFT)>>1)) * count;
  319.     }
  320.       }
  321.     }
  322.  
  323.   // - Naturally, it was brutally rewritten by E.P.
  324.   color.r = (BYTE) ((c0total + (total>>1)) / total);
  325.   color.g = (BYTE) ((c1total + (total>>1)) / total);
  326.   color.b = (BYTE) ((c2total + (total>>1)) / total);
  327. }
  328.  
  329.  
  330. void color_selector:: select_colors () {
  331. /* Master routine for color selection */
  332.   int i,j;
  333.  
  334.   /* Allocate workspace for box list */
  335.   // boxlist = (boxptr) (*cinfo->emethods->alloc_small) (desired * SIZEOF(box));
  336.   boxlist =  new box[desired_colors];
  337.   /* Initialize one box containing whole space */
  338.   numboxes = 1;
  339.   boxlist[0].c0min = 0;
  340.   boxlist[0].c0max = (1 << HIST_R_BITS )- 1;
  341.   boxlist[0].c1min = 0;
  342.   boxlist[0].c1max = (1 << HIST_G_BITS) - 1;
  343.   boxlist[0].c2min = 0;
  344.   boxlist[0].c2max = (1 << HIST_B_BITS) - 1;
  345.   /* Shrink it to actually-used volume and set its statistics */
  346.   update_box(& boxlist[0]);
  347.   /* Perform median-cut to produce final box list */
  348.   median_cut();
  349.   /* Compute the representative color for each box, fill my_colorhist[] */
  350.   for (i = 0; i < numboxes; i++) {
  351.     compute_color(& boxlist[i], my_colormap[i]);
  352.     }
  353.   actual_number_of_colors = numboxes;
  354.   delete boxlist;
  355. }
  356.  
  357. /*
  358.  * Initialize for two-pass color quantization.
  359.  */
  360.  
  361. color_selector::color_selector(int desired_colors_,int width_){
  362.   int i;
  363.  
  364.   initialized = FALSE;
  365.   desired_colors = desired_colors_;
  366.   width = width_;
  367.   /* Lower bound on # of colors ... somewhat arbitrary as long as > 0 */
  368.   if (desired_colors_ < 8) return;
  369.   if (desired_colors_ > MAXNUMCOLORS) return;
  370.  
  371.     /* Allocate and zero the hist */
  372.  
  373.     /* I killed thoroughly distingued types of memory allocation - E.P.*/
  374.     histogram = new hist2d[HIST_R_ELEMS];
  375.     for (i = 0; i < HIST_R_ELEMS; i++) histogram[i] = NULL;
  376.  
  377.  
  378.     for (i = 0; i < HIST_R_ELEMS; i++) {
  379.         histogram[i] = (hist2d) new histcell[HIST_G_ELEMS][HIST_B_ELEMS];
  380.         if (histogram[i] == NULL) return;
  381.         memset(histogram[i],0,HIST_G_ELEMS*HIST_B_ELEMS * sizeof(histcell));
  382.     }
  383.  
  384.     initialized = TRUE;
  385. }
  386.  
  387. color_selector::~color_selector() {
  388.     int i;
  389.     for (i = 0; i < HIST_R_ELEMS; i++)  if (histogram[i] != NULL) delete histogram[i];
  390.     delete histogram;
  391. }
  392.  
  393.  
  394.